package com.wxweven.algorithm.btree;

/**
 * @author wxweven
 */
public class LC654根据数组构建最大二叉树 {

    /*
     * 题目链接：https://leetcode-cn.com/problems/maximum-binary-tree/
     *
     * 给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下：
     *
     * 二叉树的根是数组 nums 中的最大元素。
     * 左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
     * 右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。
     * 返回有给定数组 nums 构建的 最大二叉树 。
     *
     * 讲解参见：https://www.yuque.com/wxweven/yn3rzz/fh3afi
     */

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return helper(nums, 0, nums.length - 1);
    }

    public TreeNode helper(int[] nums, int start, int end) {
        if (start > end) {
            return null;
        }

        // int max = Integer.MIN_VALUE;
        int max = nums[start];
        int index = start;
        for (int i = start; i <= end; i++) {
            if (max < nums[i]) {
                max = nums[i];
                index = i;
            }
        }

        TreeNode root = new TreeNode(max);
        root.left = helper(nums, start, index - 1);
        root.right = helper(nums, index + 1, end);

        return root;
    }
}